//  https://leetcode-cn.com/problems/two-sum
//  TwoCountSum.swift
//  LeetCodeSwift
//
//  Created by XFB on 2019/7/27.
//  Copyright © 2019 XFB. All rights reserved.
//  两数和

import Foundation

class TwoCountSum {
    
    /**
     给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
     你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
     
     示例:
     给定 nums = [2, 7, 11, 15], target = 9
     因为 nums[0] + nums[1] = 2 + 7 = 9
     所以返回 [0, 1]
     */
    
    /// 时间复杂度 O(N)
    /// 控件复杂度
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        
        var dict = [Int : Int]()
        
        /// index(key) -> 0, 1, 2, 3
        /// value      -> 2, 7, 11, 15
        for (index, value) in nums.enumerated() {
            /// 如果target-value作为key value就是上面的index
            /// (0, 2) (1, 7) (2, 11) (3, 15)
            /// lastIndex = dict[9-2] = dict[7]
            /// lastIndex = dict[9-7] = dict[2]
            /// 如果有值就会直接进入下一步 如果没有值就会进入else判断
            if let lastIndex = dict[target-value] {
                return [lastIndex, index]
            } else {
                /// dict[2] = 0
                /// dict[7] = 1
                dict[value] = index
            }
            /// dict[9-2] = dict[7] 不存在进入 else dict[2] = 0
            /// dict[9-7] = dict[2] 存在进入下一步 lastIndex = dict[9-7] = 0
            /// 此时lastIndex = 0, index = 1
        }
        fatalError("No Valid outputs")
    }
    
    
    /// 时间复杂度O(N)
    func twoSum1(_ nums: [Int], _ target: Int) -> [Int] {
        
        var array = [Int]()
        /// 集合
        var containers = Set<Int>()
        
        /// value = 2, 7, 11, 15
        for (index, value) in nums.enumerated() {
            /// num = 7, 2
            let num = target - value
            if containers.contains(num) {
                let firstIndex = nums.firstIndex(of: num)!
                array.append(firstIndex)
                array.append(index)
                break
            } else {
                /// 用过的元素添加到Set里面，因为不能重复利用这个数组中相同元素
                /// 集合一开始是空的，没有数值 2 7
                containers.insert(value)
            }
        }
        return array
    }
    
    
    /// 时间复杂度 O(N^2)
    func twoSum2(_ nums: [Int], _ target: Int) -> [Int] {
        
        var array = [Int]()
        for i in 0 ..< nums.count {
            for j in 1 ..< nums.count {
                if nums[i] + nums[j] == target && i != j {
                    array.append(i)
                    array.append(j)
                    return array
                }
            }
        }
        return array
    }
    
}
